Ci sono casi in cui siamo interessati al fatto che, data una query, la prima risposta fornita sia corretta. Il Mean Reciprocal Rank permette di valutare la capacità di un sistema di inserire documenti rilevanti tra le prime posizioni: MRR = \dfrac{1}{|Q|} \displaystyle \sum_{i = 1}^{|Q|} \dfrac{1}{rank_i}, dove |Q| è il numero di query e rank_i è la posizione del primo documento rilevante ritrovato per la query considerata.
Più la posizione del primo documento rilevante è lontana dalla prima posizione, tanto minore sarà il suo reciproco e viceversa.
9.1 Valutazione di sistema con giudizi non binari
Precision e Recall permettono solo valutazioni di sistemi in cui la rilevanza è espressa tramite giudizi binari.
Una metrica per valutare sistemi la cui rilevanza è espressa su scale a più valori è la Discounted Cumulative Gain
Principi della DCG:
I documenti molto rilevanti sono più utili dei documenti marginalmente rilevanti (un documento valutato 8 su 10 è più utile di uno valutato 5 su 10)
E’ preferibile che i documenti più rilevanti siano in cima ai risultati poiché la loro utilità diminuisce proporzionalmente alla profondità della loro posizione.
La DCG è calcolata in più fasi:
G = Gain vector: quantifichiamo i due principi a partire da un gain vector, ovvero un vettore in cui l’esperto esprime, secondo la scala utilizzata, la rilevanza dei documenti ritrovati (tagliando la lista magari ai primi 15 risultati).
D = Discounted: smorziamo l’impatto dei gain man mano che ci muoviamo in profondità nel ranking utilizzando il logaritmo: DCG_j[i] = \begin{cases} G_j [1] \; \; \; \text{if i = 1} \\ \dfrac{G_j[i]}{\log_2 i} + DCG_j[i - 1] \; \; \; \text{i > 1} \end{cases}
A questo punto è possibile utilizzare il CG o il DCG su un insieme di query semplicemente facendo la media del CG o DCG per ogni posizione sul numero delle query: CG_m[i] = \displaystyle \sum_{j = 1}^{N_q} \dfrac{CG_j[i]}{N_q}
Problema: il confronto tra algoritmi di ranking diversi non è possibile data la mancanza di una baseline.
Soluzione: utilizzare l’Ideal Gain Vector, ovvero un vettore creato ordinando tutti i punteggi di rilevanza in ordine decrescente
A questo punto si eseguono gli stessi calcoli precedenti, quindi si ottiene l’ICG, l’IDCG e poi si fa la media tra le query. In questo modo abbiamo una base di confronto
L’Ideal viene poi utilizzato per normalizzare CG e DCG: NCG[i] = \dfrac{CG_m[i]}{ICG_m[i]}
L’area sotto le curve di NCG e NDCG rappresentano la qualità del ranking, maggiore è l’area, migliori sono i risultati. Quindi, curve normalizzate possono essere utilizzate per confrontare algoritmi di ranking differenti
Rank correlation: Precision e recall permettono di comparare la rilevanza dei risultati prodotti da due funzioni di ranking. Però, ci sono casi in cui non è possibile misurare direttamente la rilevanza, o perché non c’è una raccolta di giudizi di rilevanza fatta da esperti, o perché siamo interessati a confrontare un algoritmo da testare con uno il cui buon funzionamento è noto. Questo può essere fatto utilizzando funzioni statistiche chiamate metriche di rank correlation.
Una metrica di rank correlation che confronta due funzioni di ranking R1 e R2 rispetta le seguenti proprietà:
-1 \leq C(R_1, R_2) \leq 1
se C(R_1, R_2) = 1, i due algoritmi sono completamente d’accordo (sono uguali)
se C(R_1, R_2) = -1, i due algoritmi sono completamente in disaccordo (sono uno il reverse dell’altro)
se C(R_1, R_2) = 0, i due ranking sono completamente indipendenti
Coefficiente di Spearman: si basa sulle differenze tra le posizioni dello stesso documento nei due ranking a confronto. Per enfatizzare la distanza si calcola il quadrato delle distanze. Per produrre poi una valutazione quantitativa, sommiamo le differenze per ogni coppia ordinata
In generale, data una lista di K documenti, il massimo valore per la somma dei quadrati vale \dfrac{K \cdot (K^2 - 1)}{3}
A questo punto “normalizziamo” la somma delle distanze quadratiche con il massimo valore per la somma dei quadrati:
Coefficiente di Kendall Tau: prendiamo due documenti e le loro posizioni nei due ranking in maniera indipendente tra loro. Quindi, verifico in che ordine i documenti si trovano. Se l’ordine è lo stesso, la coppia di documenti (d_k, d_j) è concorde, altrimenti è discorde.
Consideriamo tutte le coppie ordinate dei due ranking e verifichiamo se siano concordi o meno tra i ranking. Infine, contiamo il numero di coppie concordi e discordi tra i due ranking e calcoliamo la differenza: \tau(R_1, R_2) = P(R_1 = R_2) - P(R_1 \neq R_2)